Perceptron
Działanie perceptronu można opisać zależnością :::: n y = f(J2WiXi+0)- /=i Zauważmy, że wzór (6.3) koresponduje z ogólnym zapisem (6.1), jeżeli 0 = wq. Funkcja / może być nieciągłą funkcją skokową — bipolarną (przyjmuje wartości -1 lub 1) lub unipolarną (przyjmuje wartości 0 lub I). Do dalszych rozważań przyjmiemy, iż funkcja aktywacji jest bipolarna 1. gdy 5 > 0. -1, gdy s < 0. Perceptron ze względu na swą funkcję aktywacji przyjmuje tylko dwie różne wartości wyjściowe, może więc klasyfikować sygnały podane na jego wejście w postaci wektorów x = ,..., a„r do jednej z dwóch klas. Na przykład perceptron z jednym wejściem może oceniać, czy sygnał wejściowy jest dodatni, czy ujemny. W przypadku dwóch wejść x\ i x2 perceptron dzieli płaszczyznę na dwie części. Podział ten wyznacza prosta o równaniu :::: w\X\ + w2x 2 + 0 = 0. (6.5) Zatem równanie (6.5) można napisać :::: w i 9 x2 =------------ -vi----------- . W2 XV 2 W ogólnym przypadku, gdy perceptron ma n wejść, wówczas dzieli n-wymiarową przestrzeń wektorów wejściowych x na dwie pólprzestrzenie. Są one rozdzielone n — 1-wymiarową hiperpłaszczyzną, nazywaną granicą decyzyjną, daną wzorem :::: 'i Y^ *i + 0 = 0. i=l Na rysunku 6.4 przedstawiono granicę decyzyjną dla n = 2. Należy zauważyć, że prosta wyznaczająca podział przestrzeni jest zawsze prostopadła do wektora wag W = , wT. :::: Rys. 6.4. Granica decyzyjna dla n = 2 Zgodnie z tym, co napisaliśmy we wstępie, perceptron można uczyć. W czasie tego procesu jego wagi są modyfikowane. Metoda uczenia perceptronu należy do grupy algorytmów zwanych uczeniem z nauczycielem lub uczeniem nadzorowanym. Uczenie tego typu polega na tym. iż podaje się na wejście perceptronu sygnały \{t) = [*o(/).*i(0 x„(t)Yy t = 1.2 dla których znamy prawidłowe wartości sygnałów wyjściowych d(t), t = 1,2,..., zwanych sygnałami wzorcowymi. Zbiór takich próbek wejściowych wraz z odpowiadającymi im wartościami sygnałów wzorcowych nazywamy ciągiem uczącym. W metodach tych po podaniu wartości wejściowych oblicza się sygnał wyjściowy neuronu. Następnie modyfikuje się wagi w ten sposób, aby minimalizować błąd między sygnałem wzorcowym a wyjściem perceptronu. Stąd właśnie nazwa „uczenie z nauczycielem", ponieważ nauczyciel określa, jaka powinna być wartość wzorcowa. Oczywiście można się domyślać, iż istnieją algorytmy uczące sieci bez nauczyciela, ale o nich napiszemy w następnych punktach tego rozdziału. Algorytm uczenia perceptronu przedstawia się następująco: 1. Wybieramy w sposób losowy wagi początkowe perceptronu. 2. Na wejścia neuronu podajemy wektor uczący x. przy czym x = x(0 = [*o(/), jfi(/),...,*»(f)r,/= 1.2 3. Obliczamy wartość wyjściową perceptronu y, zgodnie ze wzorem (6.3). 4. Porównujemy wartość wyjściową y® z wartością wzorcową d = d(x(t)) znajdującą się w ciągu uczącym. 5. Dokonujemy modyfikacji wag według zależności: a) jeżeli y(x(/)) ^ d(x(f)), to w,(t + 1) = Wi{t) + d(x(/))*,(/); b) jeżeli y(x(0) = ć/(x(/)), to u?r-(/ + l)=u;,-(0> czyli wagi pozostają bez zmian. 6. Wracamy do punktu 2. Algorytm powtarza się tak długo, aż dla wszystkich wektorów wejściowych wchodzących w skład ciągu uczącego błąd na wyjściu będzie mniejszy od założonej tolerancji. Na rysunku 6.5 przedstawiono schemat blokowy uczenia perceptronu. Działanie pętli wewnętrznej na tym rysunku dotyczy tzw. jednej epoki, na którą składają się dane tworzące ciąg uczący. Działanie pętli zewnętrznej odzwierciedla możliwość wielokrotnego stosowania tego samego ciągu uczącego, aż zostanie spełniony warunek zatrzymania algorytmu. Wykażemy, iż algorytm uczenia perceptronu jest zbieżny. Twierdzenie o zbieżności algorytmu uczenia perceptronu formułuje się następująco: Jeżeli istnieje zestaw wag w* = .......... w*]T klasyfikujący wzorce uczące x = 1*1,..., .v„ l7 poprawnie, tzn. wyznaczający odwzorowanie y = d{x), to algorytm uczący znajdzie rozwiązanie w skończonej liczbie iteracji dla dowolnych wartości początkowych wektora wag >v. Zakładamy, że dane uczące reprezentują klasy liniowo separowane, gdyż tylko wtedy można nauczyć perceptron. Pokażemy, że istnieje skończona liczba kroków modyfikacji wag, po których perceptron będzie realizował odwzorowanie y = d(x). Ze względu na to, że funkcja aktywacji w perceptronie jest typu sgn, długość wektora w* możemy przyjąć dowolną, np. równą 1, tzn. ||w*|| = 1. Zatem w czasie uczenia wektor w I Losowy dobór wag perceptronu £ i = I |} wystarczy modyfikować tak. aby pokazany na rysunku 6.6 kąt a był równy 0. Oczywiście wtedy cos(a) = 1. Z faktu, że |w# o x| > 0 (znak o w tym przypadku oznacza iloczyn skalarny wektorów) i w* jest rozwiązaniem, wynika istnienie takiej stałej 8 > 0. dla której jw" ox| > <5 dla wszystkich wektorów x z ciągu uczącego. Z definicji iloczynu skalar ncgo wynika, że ::::: w* o w cos (a) = =. (6.8) yi|w*|2||w|p Ponieważ = i. (6.9) więc ::::: w* o w cos(of) = —-——. (6.10) II w || Zgodnie z algorytmem uczenia perceptronu, wagi modyfikowane są dla podanego wektora wejściowego x według następującej zależności: w' = w + Aw. gdzie Aw = d(x)x. Oczywiście zakładamy, że na wyjściu sieci pojawił się błąd i korekcja wag jest niezbędna. Zauważmy, że ::: w' o w* = w o w* + d(x)w* o x (6.11) = w o w* + sgn(w o x)w* o x. (6.12) Zachodzą następujące fakty: (i) Jeżeli w*ox < 0. to sgn(w*ox) = -1. więc sgn(w*ox)w*ox = — l(w*ox) > 0, (ii) Jeżeli w* o x > 0. to sgn(w* o x) = 1. więc sgn(w* o x)w* o x = 1 (w* o x) > 0. Zatem ::: sgn(w* o x)w* o x = |w*ox|. (6.13) Zgodnie ze wzorami (6.12) i (6.13) możemy napisać w' O W* = w O w* + | w* O XI. (6.14) Wiemy też, że |w* o x| > 8, stąd ::: w'ow*>wow * + 8. (6.15) Oszacujmy teraz wartość ||w'||2, pamiętając jednocześnie, iż rozpatrujemy przypadek, kiedy po podaniu na wejście wektora uczącego x na wyjściu sieci pojawia się błąd. tzn. d(x) — —sgn(w o x). (6.16) Oczywiście l|w'||2 = ||w + 2 = ||w||2 + 2d(x)w o x + ||x||2. (6.17) Wykorzystując zależności (6.16) i (6.17) oraz zakładając ograniczoność sygnałów wejściowych. mamy ::: IIw'II2 < l|w||2 +||x||2 = ||w||2 + C. (6.18) Po / krokach mcxlyfikacji wag sieci zależności (6.15) oraz (6.18) przybierają postać w(0 o w* > w o wx + tS (6.19) oraz ||w(/)||2 < ||w||2 + tC. (6.20) Korzystając ze wzorów (6.10), (6.19) i (6.20), otrzymujemy w* o w® w" o w + tS cos a(t) = — > ; (6.21) IIw (011 y||w||2 + /C Dlatego też musi istnieć takie t = /max, dla którego cos(a) = 1. A więc istnieje skończona liczba kroków modyfikacji wag, po których wektor wag początkowych będzie realizował odwzorowanie y = d(x). Jeżeli przyjmiemy, że wartości startowe wag są równe 0. to ::::: C 'max = (6.22) Przykład 6.1 Przedstawimy teraz przykład uczenia perceptronu. Omawiając jego działanie, stwierdziliśmy, iż ten model neuronu o dwóch wejściach dzieli płaszczyznę na dwie części (por. (6.5)). Wobec tego. jeżeli na płaszczyźnie umieścimy dwie klasy próbek, które będzie można rozdzielić za pomocą prostej, to perceptron w procesie uczenia będzie w stanie znaleźć tę linię podziału. W naszym doświadczeniu wykreślimy prostą wzorcową, oznaczoną literą L na rysunku 6.7. Przyjmiemy, że wszystkie punkty płaszczyzny leżące nad tą prostą reprezentują próbki z klasy 1, natomiast punkty leżące pod prostą L reprezentują klasę 2. Takich punktów na obu półpłaszczyznach znajduje się nieskończenie wiele i dlatego musimy wybrać po kilka próbek z każdej klasy. Chcemy, aby perceptron po nauczeniu dla próbek z klasy pierwszej na wyjściu podawał sygnał równy 1, natomiast dla próbek z klasy drugiej sygnał równy — 1. W ten sposób zbudowaliśmy ciąg uczący przedstawiony w tabeli 6.1. |} Przyjmujemy następujące wartości początkowe wag perceptronu: w i = 2, w 2 = 2, 0 = —4. Na podstawie tych parametrów oraz wcześniejszych informacji wykreślamy prostą K, która pokazuje podział przestrzeni (granica decyzyjna), jaki wyznacza perceptron przed rozpoczęciem procesu uczenia. Perceptron po dziesięciu epokach algorytmu uczenia (10 razy podawaliśmy na wejścia neuronu wszystkie elementy ciągu uczącego) zaczął poprawnie klasyfikować wektory ciągu uczącego. Wagi jego przyjęły następujące wartości: u;i = 4, w2 = 1, 9 — — 1, co odzwierciedla prosta M będąca granicą decyzyjną. Na rysunku 6.7 widzimy, że perceptron po nauczeniu poprawnie klasyfikuje próbki uczące, chociaż prosta M nie pokryła się z prostą wzorcową L. 6.2.3. Model Adaline Schemat neuronu Adaline (ang. Adaptive Linear Neuron) przedstawiono na rysunku 6.8 Budowa tego neuronu jest bardzo podobna do modelu perceptronu, a jedyna różnica dotyczy algorytmu uczenia. Sposób wyznaczania sygnału wyjściowego jest identyczny z przedstawionym w poprzednim punkcie dotyczącym perceptronu. Jednak w przypadku neuronu typu Adaline porównuje się sygnał wzorcowy d z sygnałem 5 na wyjściu części liniowej neuronu (sumator). Stąd pochodzi nazwa tego typu neuronów. W ten sposób otrzymujemy błąd dany wzorem z = d — s. Uczenie neuronu, czyli dobór wag, sprowadza się do minimalizacji funkcji określonej w sposób następujący: (6.24) Miarę błędu (6.24) określa się mianem błędu średniego kwadratowego. Uwzględniając tylko część liniową neuronu, możemy do modyfikacji wag użyć algorytmów gra- dientowych, gdyż funkcja celu zdefiniowana zależnością (6.24) jest różniczkowalna. Do minimalizacji tejże funkcji użyjemy metody największego spadku. Metoda ta zostanie dokładniej omówiona przy okazji opisywania algorytmu wstecznej propagacji błędów. Wagi w neuronie typu Adaline modyfikuje się zgodnie ze wzorem SQ (w,) Wi(t + 1) = Wj(t) - //- dwj w którym t] jest współczynnikiem uczenia. Zauważmy, że 9Q{Wi) _ dQ(Wj) ds dwi dWi' Ponieważ s jest funkcją liniową względem wektora wag. więc możemy napisać ::: ds ::::: = Xi. 3 w i BQ(wj) ::::: = -(d-s). 'ós Zatem zależność (6.25) przybiera postać ::: Wj(t + 1) = Wj(t) + n&Xj, gdzie S = d — s. Powyższa reguła nosi nazwę reguły delta (jest to szczególna postać tej reguły, ponieważ nie uwzględnia ona funkcji aktywacji neuronu). Na rysunku 6.9 przedstawiono schemat blokowy algorytmu uczenia neuronu typu Adaline za pomocą tej reguły. Rys. 6.9. Schemat blokowy algorytmu uczenia neuronu typu Adalinc Neurony typu Adaline można również uczyć za pomocą rekurencyjnej metody najmniejszych kwadratów (ang. Recursive Least Sąuares — RLS). Jako miarę błędu przyjmuje się następujące wyrażenie: < i Q(t) = £k'~ke2(k) = - xT(k)w(t))2, : k=l w którym A jest współczynnikiem zapominania (ang. forgetting factor) wybieranym z przedziału 1. Zauważmy, że poprzednie błędy mają mniejszy wpływ na wartość wyrażenia (6.30). Obliczając gradient miary błędu, otrzymujemy następującą zależność: 32C) aw (/) 9w (/) Ow(f) :::: / ::: = -2 £ *'-*- xr(k)w(r)x(k). k=i Optymalne wartości wag powinny spełniać tzw. równanie normalne ::: t :::: d(k) - xT(k)w(t))x{k) = 0. (6.32) *=1 Równanie (6.32) można przedstawić w postaci r(0 = R(/)w(/), (6.33) gdzie :::: i R(/) = J2>'~k^)x'\k) (6.34) jfcssl jest n x ^-wymiarową macierzą autokorelacji, oraz :::: i ::: r (f) = l'~kd(k)x(k) (6.35) k=\ jest n x 1-wymiarowym wektorem korelacji wzajemnej sygnału wejściowego i sygnału wzorcowego. Zakładamy, że sygnały te są realizacjami stacjonarnych procesów stochastycznych. Rozwiązanie równania normalnego (6.33) przybiera postać w(/) = R-,(/)r®, (6.36) jeżeli det R(/) ^ 0. Zastosujemy teraz algorytm RLS w celu uniknięcia operacji odwracania macierzy w równaniu (6.36) i rozwiążemy równanie normalne (6.33) w sposób rekurencyjny. Zauważmy, że macierz R(/) oraz wektor r(/) można przedstawić w postaci R(t) = AR(r - 1) + x(t)xT(t) (6.37) oraz r(0 = kr« - 1) + x{t)d(t). (6.38) Zastosujemy teraz lemat o odwrotności macierzy. Niech A i B będą dodatnio określonymi n x n-wymiarowymi macierzami takimi, że :::: A = B~ł + CD-lCr, (6.39) gdzie D jest dodatnio określoną m x m-wymiarową macierzą, natomiast C jest n x m- - wymiarową macierzą. Wówczas A-1 = B - BC(D + CrBC)-1CrB. (6.40) Porównując wzory (6.40) i (6.37), otrzymujemy A = R(f). B~' = AR(/ - 1), C = x(/), D= 1. P(0 = XTl- g(/)xr(/)P(f - 1), (6.42) P(/) = R-I(0 (6.43) :::: Pjt - l)x(Q______ ::: 8(0 k+xT(mt-\)x«y } Wykażemy prawdziwość następującego równania: g(/) = P (f)x®. (6.45) W wyniku prostych operacji algebraicznych otrzymujemy : = P(/-l)x(Q 6V A + xr(/)P(/ - 1 )x(/) _ k~l- l)x(/) + P(r - l)x(/)xr(/)P(f - l)x(r)J k + xT(t)P(t- 1 )x(r) A-'|P(t - l)x(r)xr(/) + P(f - l)x(0 k + xT(t)P(t — l)x(0 = A~'+ x7'(/)P(r- l)x(Q)lP(r - l)x(Q (6.46) k + xT(t)P(t - l)x(/) k~ll)x(/)xr(QP(/- l)x(/) k + xT(t)P(t - 1 )x(/) = r P(, - l)x(,),'(,) 1p(r_1)x(/) L A. 4-x (/)P(/ l)x(/)J = AT1 - g(r)xr(/)P(r - 1 )x(/) = P(/)x®. Z zależności (6.38) oraz (6.36) wynika, że w(/) = R-'(0r(/) = kP(t)r(t - 1) + P(t)x(t)d(t). (6.47) Z równania (6.42) oraz (6.47) otrzymujemy :: w(f) = - g(/)xr(/)P(/ - l)r(/ - 1) + P(/)x®J(/). (6.48) Konsekwencją zależności (6.38) i (6.36) jest następujący związek: :: w(/) = w(/ - 1) - g(/)xT(/)w(/ - 1) + P(t)x(ł)d(t). (6.49) Uwzględniając związek (6.45) w zależności (6.49). otrzymujemy następującą rekursję: w® = w(t - 1) + z(t)- xr(/)w(t - 1)J. (6.50) W konsekwencji algorytm RLS zastosowany do uczenia neuronu typu Adaline przybiera następującą postać: £(t) = d{t) - xT(t)w(t - 1) = d(t) - y(r), (6.51) :: P(/) = A_1[I - g(Oxr(r)P(/ - 1), (6.53) w(/) = w(r-l) + g(/)£®. (6.54) Jako wartości początkowe zazwyczaj przyjmuje się ::: P(0) = yh y > 0, (6.55) gdzie y jest stałą, natomiast I jest macierzą jednostkową.